Capacity Regions of Two-Receiver Broadcast Erasure Channels with Feedback and Memory

摘要

The two-receiver broadcast packet erasure channel with feedback and memory isstudied. Memory is modeled using a finite-state Markov chain representing achannel state. Two scenarios are considered: (i) when the transmitter hascausal knowledge of the channel state (i.e., the state is visible), and (ii)when the channel state is unknown at the transmitter, but observations of itare available at the transmitter through feedback (i.e., the state is hidden).In both scenarios, matching outer and inner bounds on the rates ofcommunication are derived and the capacity region is determined. It is shownthat similar results carry over to channels with memory and delayed feedbackand memoryless compound channels with feedback. When the state is visible, thecapacity region has a single-letter characterization and is in terms of alinear program. Two optimal coding schemes are devised that use feedback tokeep track of the sent/received packets via a network of queues: aprobabilistic scheme and a deterministic backpressure-like algorithm. Theformer bases its decisions solely on the past channel state information and thelatter follows a max-weight queue-based policy. The performance of thealgorithms are analyzed using the frameworks of rate stability in networks ofqueues, max-flow min-cut duality in networks, and finite-horizon Lyapunov driftanalysis. When the state is hidden, the capacity region does not have asingle-letter characterization and is, in this sense, uncomputable.Approximations of the capacity region are provided and two optimal codingalgorithms are outlined. The first algorithm is a probabilistic coding schemethat bases its decisions on the past L acknowledgments and its achievable rateregion approaches the capacity region exponentially fast in L. The secondalgorithm is a backpressure-like algorithm that performs optimally in the longrun.